// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-06 14:54
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.TREE;

import com.DataStruct.Tree.TwoBinaryTree.TreeNode;
import com.DataStruct.Tree.TwoBinaryTree.Utils;
import org.junit.jupiter.api.Test;


public class FindTilt {
    // 方法错误

    /**
     * 计算给定二叉树的根节点的坡度之和
     * 当前节点的坡度-> 当前节点的左子树坡度 - 当前节点右子树的坡度
     */
    public int findTilt(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            // 当前节点为叶子节点
            return 0;
        }

        if (root.right != null && root.left != null) {
            if (isLeaf(root.left) && isLeaf(root.right)) {
                // 左右节点都为叶子节点
                return Math.abs(root.left.val - root.right.val);
            } else if (isLeaf(root.left)) {
                // 左节点为叶子节点右节点不为叶子节点
                return Math.abs(root.left.val - findTilt(root.right));
            } else if (isLeaf(root.right)) {
                return Math.abs(root.right.val - findTilt(root.left));
            } else {
                // 左右节点都不为叶子节点
                return Math.abs(findTilt(root.left) - findTilt(root.right));
            }
        } else {
            // 左子树或者右子树有一个为空,则返回不空的子树坡度
            if (root.left == null) {
                return findTilt(root.right);
            } else {
                return findTilt(root.left);
            }
        }
    }

    /**
     * 判断当前节点是否为叶子节点
     *
     * @param root 传入的节点
     * @return 是否为叶子节点
     */
    private boolean isLeaf(TreeNode root) {
        if (root == null) {
            return false;
        }
        return root.left == null && root.right == null;
    }

    @Test
    public void shout() {
        int[] nodes = {21, 7, 14, 1, 1, 2, 2, 3, 3};
        Utils utils = new Utils();
        TreeNode<Integer> root = utils.constructTreeBySequence(nodes);
        System.out.println(new FindTilt().findTilt(root));

    }
}
